(1) Field of the Invention
The present invention relates to a resource allocation device employed by a computer to allocate a variable to a resource when translating a source program into an object program.
(2) Description of Related Art
Development of a program has been promoted by describing a program in a high-level language such as a C language. A compiler translates a source program from a high-level language into a machine language which can be understood by a target computer.
A source program employs variables to hold numeric values to be computed in an operation or to hold operation results. Variables are defined by a programmer depending on the needs; or, they are generated by a compiler so that internal processing will be facilitated. Only a required number of the generated variables will be used.
A machine language program, on the other hand, operates a register or a memory to hold numeric values to be computed in an operation or to hold operation results. Both a register and a memory are hardware, so that the number of registers and memories which can be employed at each source program is limited.
When translating a source program into a machine language program, all the variables included in the source program need to be allocated to either a register or a memory. A conventional compiler operates a resource allocation device to allocate each variable to either a register or a memory.
A register and a memory are also called resources defined in a program and are referred to as xe2x80x9calivexe2x80x9d until their final references in the program.
Generally the number of available registers is small, so that the compiler implements the best use thereof by allocating a frequently used variable to a register. To be concrete, the compiler determines the frequency each variable used in a source program, and divides the frequency of appearance of the variable by its live range, which indicates how long the variable is alive. Then, the variable with a large dividing result will be allocated to a register while the variable with a small dividing result will be allocated to a memory.
According to the conventional compiler, however, size and run time of the translated machine language program are not considered when allocating a variable to a resource. That is, when allocating a variable to either a register or a memory, an operation including the variable and an instruction sequence replacing the operation are not considered; consequently, size of the machine language program including a plurality of the instruction sequences tends to be large. As a result, run times of such machine language programs are often long.
For example, it is assumed that a target machine manipulates operand at registers. With the allocation by the conventional resource allocation device, a variable x representing the operand in the machine language program may be allocated to a memory. In this case, a transfer instruction which directs transfer of the content of the memory to the register must be included in the machine language program. If a number of the transfer instructions are included in the machine language program, size of the program will be expanded and run time thereof will be extended by the transfer instructions.
Accordingly, it is an object of the present invention to provide a resource allocation device for reducing run time and size of a machine language program.
The above object may be fulfilled by a resource allocation device employed by a compiler for translating a high-level language program or a program translated from the high-level language program by a compiler for its internal processing, into a machine language of a target machine, the resource allocation device allocating a variable included in a resource allocation portion of the program to a resource such as a register or a memory, the resource allocation portion being subjected to the resource allocation, the resource allocation device comprising a variable holding unit for holding all live variables placed within the resource allocation portion, a pattern generation unit for generating every pattern of the resource and each variable held by the variable holding unit, the variable to be allocated to the resource, an instruction sequence holding unit for holding an instruction sequence corresponding to each combination of an operation and the resource, the instruction sequence written in an assembly language and/or a macro language, an instruction extraction unit for extracting the instruction sequence for each pattern generated by the pattern generation unit in accordance with each operation placed within the resource allocation portion and the resource to which the variable in the operation is allocated, and generating a program corresponding to the resource allocation portion, the program comprising the extracted instruction sequences, a cost table for holding the instruction sequence and a cost thereof representing the number of execution clocks taken in execution of the instruction sequence, a cost detection unit for detecting from the cost table the cost of each instruction sequence included in each program generated by the instruction extraction unit, a total cost computation unit for computing a total cost of each pattern generated by the pattern generation unit as referring to the cost of each instruction sequence detected by the cost detection unit, and a best pattern decision unit for deciding the pattern with the lowest cost in the patterns generated by the pattern generation unit as referring to the total cost of each pattern.
The pattern generation unit may be comprised of a first variable selection unit for selecting all the variables held by the variable holding unit unless a predetermined direction is given by a user; a variable evaluation unit for obtaining a variable evaluation value of each live variable by dividing the number of the operations referring to/defining the live variable by its live range; a second variable selection unit for arranging the variables by the variable evaluation values and selecting a predetermined number of the variables which starts with a first variable with the largest variable evaluation value and ends with a final variable so that the number of the selected variables including the first and the final variables coincides with the predetermined number; and a generation unit for generating every pattern of the variables selected by the first variable selection unit or the second variable selection unit and the resource corresponding to each of the variables.
The second variable selection unit may be comprised of a computation unit for computing the predetermined number by doubling the number of the registers employed by the target machine; a first selection unit for selecting all the variables from the resource allocation portion when the number of the selected variables is the predetermined number or smaller than the same; and a second selection unit for arranging the variables by the variable evaluation values and selecting the predetermined number of variables which starts with a first variable with the largest evaluation value and ends with a final variable so that the number of the selected variables including the first and the final variables coincides with the predetermined number computed by the computation unit when the number of the variables placed within the resource allocation portion is larger than the predetermined number.
The instruction sequence holding unit may hold the instruction sequence which corresponds to a combination of an action type, a variable type, an operand, and a storage in which the action type, the variable type, and the operand are included in the operation while results of the operation are stored into the storage; and an instruction extraction unit may extract the instruction sequence for each pattern generated by the pattern generation unit as referring to the action type, the variable type, and the operand, all of which are included in the operation placed within the resource allocation portion as well as referring to a resource to which the variable in the operation is allocated, and generate a program which includes the extracted instruction sequences.
The cost table may hold the instruction sequence and cost thereof, the cost representing memory size needed by the instruction sequence on a memory and/or the number of execution clocks taken in execution of the instruction sequence.
The above object may be fulfilled by a resource allocation device employed by a compiler for translating a high-level language program or a program translated from the high-level language program by a compiler for its internal processing, into a machine language of a target machine, the resource allocation device allocating a variable included in a resource allocation portion of a programming language program to a resource such as a register or a memory, the resource allocation portion being subjected to the resource allocation, the resource allocation device comprising a variable holding unit for holding all live variables placed within the resource allocation portion, a pattern generation unit for generating every pattern of the resource and the variable held by the variable holding unit, the variable to be allocated to the resource, a holding unit for holding an instruction sequence corresponding to each combination of an operation and the resource as well as a cost of the instruction sequence, the instruction sequence written in an assembly language and/or a macro language, an extraction unit for extracting the instruction sequence for each pattern generated by the pattern generation unit and cost thereof in accordance with each operation placed within the resource allocation portion and the resource to which the variable in the operation is allocated, and generating a program corresponding to the resource allocation portion, the program comprised of the extracted instruction sequences, a total cost computation unit for computing a total cost of each pattern generated by the pattern generation unit in accordance with the cost extracted by the extraction unit, and a best pattern decision unit for deciding a pattern with the lowest total cost in the patterns generated by the pattern generation unit as referring to the total cost of each pattern computed by the total cost computation unit.
The pattern generation unit may be comprised of a first variable selection unit for selecting all the variables held by the variable holding unit unless a predetermined instruction is provided by a user, a variable evaluation unit for obtaining a variable evaluation value of each live variable placed within the resource allocation portion by dividing the number of the operations referring to/defining the live variable by its live range indicating how long it is alive, a second variable selection unit for arranging the variables by the variable evaluation values and selecting a predetermined number of the variables which starts with a first variable with the largest variable evaluation value and ends with a final variable so that the number of the selected variables including the first and the final variables coincides with the predetermined number, and a generation unit for generating every pattern of each variable selected by one of the first variable selection unit or the second variable selection unit as well as the resource to which each variable is allocated.
The second variable selection unit may be comprised of a computation unit for computing the predetermined number by doubling the number of the registers assigned to the target machine, a first selection unit for selecting all the variables placed within the resource allocation portion when the number of the selected variables is the predetermined number computed by the computation unit or smaller than the same, and a second selection unit for arranging the variables by the variable evaluation values and selecting the predetermined number of variables which starts with a first variable with the largest evaluation value and ends with a final variable so that the number of the selected variables including the first and the final variables coincides with the predetermined number when the number of the variables placed within the resource allocation portion is larger than the predetermined number computed by the computation unit.
The holding unit may hold the instruction sequence and cost thereof, the instruction sequence being written in an assembly language and/or a macro language and corresponding to a combination of an action type, a variable type, an operand, and a storage in which the action type, the variable, and the operand are included in the operation while results of the operation are stored into the storage; and the extraction unit may extract the instruction sequence for each pattern generated by the pattern generation unit as referring to the action type, the variable type, and the operand, all of which are included in each operation placed within the resource allocation portion, as well as referring to the resource to which the variable in the operation is allocated, and generate a program corresponding to the resource allocation portion, the program comprised of the extracted instruction sequences.
The holding unit may hold the instruction sequence and its cost which represents memory size needed by the instruction sequence on a memory and/or the number of execution clocks taken in execution of the instruction sequence.
According to the present invention, an instruction sequence which replaces an operation is stored into an instruction storage and the number of cycles and/or memory size taken in execution of each instruction sequence is recorded in a cost table. A pattern of a resource and a variable allocated to the resource is generated, and as referring to the cost table a total cost of operations which are placed within a part of a program subjected to resource allocation is computed for each pattern. Consequently, the pattern with the lowest cost is detected, and resource allocation is conducted in accordance with the detected pattern. As a result, the size and the run time of the machine language program will be reduced.